package org.czl.gh;

public class kmp {
    public static void main(String[] args) {
        //[21,22,21,22,21,22,21,30]
        System.out.println(canChoose(new int[][]{{1,2,3},{3,4}}, new int[]{1,2,3,3,4}));
    }
    public static boolean canChoose(int[][] groups, int[] nums) {
        int m = groups.length;
        int n = groups[0].length;
        int[][] next = new int[m][n];
        for(int i = 0; i < m; i++){
            int maxLen = 0;
            for(int j = 1; j < n; j++){
                while(maxLen > 0 && nums[j] != nums[maxLen]){
                    maxLen = next[i][maxLen - 1];
                }
                if(nums[j] == nums[maxLen]){
                    maxLen++;
                }
                next[i][j] = maxLen;
            }
        }
        int count = 0;
        int c = nums.length;
        int index = 0;
        for(int i = 0; i < c; i++){
            while(count > 0 && nums[i] != groups[index][count]){
                count = next[index][count - 1];
            }
            if(nums[i] == groups[index][count]){
                count++;
            }
            if(count == n){
                index++;
                if(index == m)return true;
                count = 0;
            }
        }
        return index >= m;
    }
}
